SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Streaming algorithm</title>

</head>

Streaming algorithm

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, streaming algorithms process input <a href="Data_stream" title="Data stream">data streams</a> as a <a href="Sequence" title="Sequence">sequence</a> of items, typically making just <a href="One-pass_algorithm" title="One-pass algorithm">one pass</a> (or a few passes) through the data. These algorithms are designed to operate with limited memory, generally <a href="L_(complexity)" title="L (complexity)">logarithmic</a> in the size of the stream and/or in the maximum value in the stream, and may also have limited processing time per item.

As a result of these constraints, streaming algorithms often produce approximate answers based on a summary or "sketch" of the data stream.

/* start https://en.wikipedia.org/ */

.mw-parser-output .toclimit-2 .toclevel-1 ul,.mw-parser-output .toclimit-3 .toclevel-2 ul,.mw-parser-output .toclimit-4 .toclevel-3 ul,.mw-parser-output .toclimit-5 .toclevel-4 ul,.mw-parser-output .toclimit-6 .toclevel-5 ul,.mw-parser-output .toclimit-7 .toclevel-6 ul{display:none}

/* end https://en.wikipedia.org/ */

</style><div class="toclimit-3"><meta property="mw:PageProp/toc"></div>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

Though streaming algorithms had already been studied by Munro and Paterson<a href="#cite_note-1">[1]</a> as early as 1978, as well as <a href="Philippe_Flajolet" title="Philippe Flajolet">Philippe Flajolet</a> and G. Nigel Martin in 1982/83,<a href="#cite_note-:0-2">[2]</a> the field of streaming algorithms was first formalized and popularized in a 1996 paper by <a href="Noga_Alon" title="Noga Alon">Noga Alon</a>, <a href="Yossi_Matias" title="Yossi Matias">Yossi Matias</a>, and <a href="Mario_Szegedy" title="Mario Szegedy">Mario Szegedy</a>.<a href="#cite_note-:1-3">[3]</a> For this paper, the authors later won the <a href="G%C3%B6del_Prize" title="Gödel Prize">Gödel Prize</a> in 2005 "for their foundational contribution to streaming algorithms." There has since been a large body of work centered around data streaming algorithms that spans a diverse spectrum of computer science fields such as theory, databases, networking, and natural language processing.

Semi-streaming algorithms were introduced in 2005 as a relaxation of streaming algorithms for graphs,<a href="#cite_note-4">[4]</a> in which the space allowed is linear in the number of vertices <var style="padding-right: 1px;">n</var>, but only logarithmic in the number of edges <var style="padding-right: 1px;">m</var>. This relaxation is still meaningful for dense graphs, and can solve interesting problems (such as connectivity) that are insoluble in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(n)}</annotation>

</semantics>

</math><img src="./afdac2125205278017cf549e9b004f8f6fd829c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.332ex; height:2.843ex;" alt="{\displaystyle o(n)}" loading="lazy"> space.

<div class="mw-heading mw-heading2"><h2 id="Models">Models</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Data_stream_model">Data stream model</h3></div>

In the data stream model, some or all of the input is represented as a finite sequence of integers (from some finite domain) which is generally not available for <a href="Random_access" title="Random access">random access</a>, but instead arrives one at a time in a "stream".<a href="#cite_note-5">[5]</a> If the stream has length <var style="padding-right: 1px;">n</var> and the domain has size <var style="padding-right: 1px;">m</var>, algorithms are generally constrained to use space that is <a href="L_(complexity)" title="L (complexity)">logarithmic</a> in <var style="padding-right: 1px;">m</var> and <var style="padding-right: 1px;">n</var>. They can generally make only some small constant number of passes over the stream, sometimes just <a href="One-pass_algorithm" title="One-pass algorithm">one</a>.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Turnstile_and_cash_register_models">Turnstile and cash register models</h3></div>

Much of the streaming literature is concerned with computing statistics on

frequency distributions that are too large to be stored. For this class of

problems, there is a vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a} =(a_{1},\dots ,a_{n})}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {a} =(a_{1},\dots ,a_{n})}</annotation>

</semantics>

</math><img src="./edb03646ff4cce57a23334bb76c80d6b4ccd6f67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.118ex; height:2.843ex;" alt="{\displaystyle \mathbf {a} =(a_{1},\dots ,a_{n})}" loading="lazy">

(initialized to the zero vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {0} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {0} }</annotation>

</semantics>

</math><img src="./62e8c650763635a93ddc69768c3c0c100afe985d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.337ex; height:2.176ex;" alt="{\displaystyle \mathbf {0} }" loading="lazy">) that has updates presented to it in a stream. The goal of these algorithms is to compute

functions of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {a} }</annotation>

</semantics>

</math><img src="./1a957216653a9ee0d0133dcefd13fb75e36b8b9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.299ex; height:1.676ex;" alt="{\displaystyle \mathbf {a} }" loading="lazy"> using considerably less space than it

would take to represent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {a} }</annotation>

</semantics>

</math><img src="./1a957216653a9ee0d0133dcefd13fb75e36b8b9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.299ex; height:1.676ex;" alt="{\displaystyle \mathbf {a} }" loading="lazy"> precisely. There are two

common models for updating such streams, called the "cash register" and

"turnstile" models.<a href="#cite_note-turnstile-7">[7]</a>

In the cash register model, each update is of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle i,c\rangle }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle i,c\rangle }</annotation>

</semantics>

</math><img src="./49a2255dcc99aad2487ea2c162a5558d0e0986f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle \langle i,c\rangle }" loading="lazy">, so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math><img src="./0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"> is incremented by some positive

integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">. A notable special case is when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=1}</annotation>

</semantics>

</math><img src="./3e3467f9e219a5ea38a30da5c3a02c2c23f61a79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c=1}" loading="lazy">

(only unit insertions are permitted).

In the turnstile model, each update is of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle i,c\rangle }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle i,c\rangle }</annotation>

</semantics>

</math><img src="./49a2255dcc99aad2487ea2c162a5558d0e0986f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle \langle i,c\rangle }" loading="lazy">, so that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math><img src="./0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"> is incremented by some (possibly negative) integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">. In the "strict turnstile" model, no

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math><img src="./0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"> at any time may be less than zero.

<div class="mw-heading mw-heading3"><h3 id="Sliding_window_model">Sliding window model</h3></div>

Several papers also consider the "sliding window" model. In this model,

the function of interest is computing over a fixed-size window in the

stream. As the stream progresses, items from the end of the window are

removed from consideration while new items from the stream take their

place.

Besides the above frequency-based problems, some other types of problems

have also been studied. Many graph problems are solved in the setting

where the <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> or the <a href="Adjacency_list" title="Adjacency list">adjacency list</a> of the graph is streamed in

some unknown order. There are also some problems that are very dependent

on the order of the stream (i.e., asymmetric functions), such as counting

the number of inversions in a stream and finding the longest increasing

subsequence.

<div class="mw-heading mw-heading2"><h2 id="Evaluation">Evaluation</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

The performance of an algorithm that operates on data streams is measured by three basic factors:

<ul><li>The number of passes the algorithm must make over the stream.</li>

<li>The available memory.</li>

<li>The running time of the algorithm.</li></ul>

These algorithms have many similarities with <a href="Online_algorithms" class="mw-redirect" title="Online algorithms">online algorithms</a> since they both require decisions to be made before all data are available, but they are not identical. Data stream algorithms only have limited memory available but they may be able to defer action until a group of points arrive, while online algorithms are required to take action as soon as each point arrives.

If the algorithm is an approximation algorithm then the accuracy of the answer is another key factor. The accuracy is often stated as an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\epsilon ,\delta )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\epsilon ,\delta )}</annotation>

</semantics>

</math><img src="./7c713274f5fc4c0c8a1a8e561c72314c0c5f0db6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.836ex; height:2.843ex;" alt="{\displaystyle (\epsilon ,\delta )}" loading="lazy"> approximation meaning that the algorithm achieves an error of less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"> with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-\delta }</annotation>

</semantics>

</math><img src="./e7fc18b68a939b8f9eb465e354a64164a1202901.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.052ex; height:2.509ex;" alt="{\displaystyle 1-\delta }" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Streaming algorithms have several applications in <a href="Computer_network" title="Computer network">networking</a> such as

monitoring network links for <a href="Elephant_flow" title="Elephant flow">elephant flows</a>, counting the number of

distinct flows, estimating the distribution of flow sizes, and so

on.<a href="#cite_note-8">[8]</a> They also have applications in

databases, such as estimating the size of a <a href="Join_(SQL)" title="Join (SQL)">join</a> .

<div class="mw-heading mw-heading2"><h2 id="Some_streaming_problems">Some streaming problems</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Frequency_moments">Frequency moments</h3></div>

The kth frequency moment of a set of frequencies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {a} }</annotation>

</semantics>

</math><img src="./1a957216653a9ee0d0133dcefd13fb75e36b8b9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.299ex; height:1.676ex;" alt="{\displaystyle \mathbf {a} }" loading="lazy"> is defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}}</annotation>

</semantics>

</math><img src="./a6a6b311afa34a08b23a15dedb46fa46c49534ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:14.851ex; height:6.843ex;" alt="{\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}}" loading="lazy">.

The first moment <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{1}}</annotation>

</semantics>

</math><img src="./100c7fbf174fe8b06eacc2a6b0bb2e1badd1c7ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{1}}" loading="lazy"> is simply the sum of the frequencies (i.e., the total count). The second moment <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{2}}</annotation>

</semantics>

</math><img src="./0fd17e0779153d765b40ebef91533489b87b2e37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{2}}" loading="lazy"> is useful for computing statistical properties of the data, such as the <a href="Gini_coefficient" title="Gini coefficient">Gini coefficient</a>

of variation. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{\infty }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{\infty }}</annotation>

</semantics>

</math><img src="./6779bbb6d4509c87dd7231ebf8945cccc5771e48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.37ex; height:2.509ex;" alt="{\displaystyle F_{\infty }}" loading="lazy"> is defined as the frequency of the most frequent items.

The seminal paper of Alon, Matias, and Szegedy dealt with the problem of estimating the frequency moments.

<div class="mw-heading mw-heading4"><h4 id="Calculating_frequency_moments">Calculating frequency moments</h4></div>

A direct approach to find the frequency moments requires to maintain a register mi for all distinct elements ai ∈ (1,2,3,4,...,N) which requires at least memory

of order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (N)}</annotation>

</semantics>

</math><img src="./577727c452671a036afca43509f0da81ddd7a7ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.551ex; height:2.843ex;" alt="{\displaystyle \Omega (N)}" loading="lazy">.<a href="#cite_note-:1-3">[3]</a> But we have space limitations and require an algorithm that computes in much lower memory. This can be achieved by using approximations instead of exact values. An algorithm that computes an (ε,δ)approximation of Fk, where F'k is the (ε,δ)-

approximated value of Fk.<a href="#cite_note-9">[9]</a> Where ε is the approximation parameter and δ is the confidence parameter.<a href="#cite_note-:2-10">[10]</a>

<div class="mw-heading mw-heading5"><h5 id="Calculating_F0_(distinct_elements_in_a_data_stream)">Calculating F0 (distinct elements in a data stream)</h5></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Count-distinct_problem" title="Count-distinct problem">Count-distinct problem</a></div>

<div class="mw-heading mw-heading6"><h6 id="FM-Sketch_algorithm">FM-Sketch algorithm</h6></div>

Flajolet et al. in <a href="#cite_note-:0-2">[2]</a> introduced probabilistic method of counting which was inspired from a paper by <a href="Robert_Morris_(cryptographer)" title="Robert Morris (cryptographer)">Robert Morris</a>.<a href="#cite_note-11">[11]</a> Morris in his paper says that if the requirement of accuracy is dropped, a counter n can be replaced by a counter log n which can be stored in log log n bits.<a href="#cite_note-12">[12]</a> Flajolet et al. in <a href="#cite_note-:0-2">[2]</a> improved this method by using a hash function h which is assumed to uniformly distribute the element in the hash space (a binary string of length L).

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h:[m]\rightarrow [0,2^{L}-1]}</annotation>

</semantics>

</math><img src="./019841550fa9ae67cd9100520f432f51fda3ec98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.231ex; height:3.176ex;" alt="{\displaystyle h:[m]\rightarrow [0,2^{L}-1]}" loading="lazy"></dd></dl>

Let bit(y,k) represent the kth bit in binary representation of y

</mrow>

</munder>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}}</annotation>

</semantics>

</math><img src="./e316e3000964c2a70f545c353763e0e153cfd96b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:20.496ex; height:5.843ex;" alt="{\displaystyle y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}}" loading="lazy"></dd></dl>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (y)}</annotation>

</semantics>

</math><img src="./c2377398a6f858722982fcfd6f510cc97bab1ae6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.167ex; height:2.843ex;" alt="{\displaystyle \rho (y)}" loading="lazy"> represents the position of least

significant 1-bit in the binary representation of yi with a suitable convention for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (0)}</annotation>

</semantics>

</math><img src="./dd3300b3c092a939f5e977152e2b2b66cd9f7401.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.174ex; height:2.843ex;" alt="{\displaystyle \rho (0)}" loading="lazy">.

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}}">

<mrow>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}}</annotation>

</semantics>

</math><img src="./0824e48eaf749c1985334e0e4fb2d5f026db0416.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:42.589ex; height:6.176ex;" alt="{\displaystyle \rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}}" loading="lazy"></dd></dl>

Let A be the sequence of data stream of length M whose cardinality need to be determined. Let BITMAP [0...L − 1] be the

hash space where the ρ(hashedvalues) are recorded. The below algorithm then determines approximate cardinality of A.<pre>Procedure FM-Sketch:

for i in 0 to L − 1 do

BITMAP[i] := 0

end for

for x in A: do

Index := ρ(hash(x))

if BITMAP[index] = 0 then

BITMAP[index] := 1

end if

end for

B := Position of left most 0 bit of BITMAP[]

return 2 ^ B

</pre>If there are N distinct elements in a data stream.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\gg \log(N)}</annotation>

</semantics>

</math><img src="./78e0ba7628c3af692bd2f831c300fb2d09ef5a59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.261ex; height:2.843ex;" alt="{\displaystyle i\gg \log(N)}" loading="lazy"> then BITMAP[i] is certainly 0</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\ll \log(N)}</annotation>

</semantics>

</math><img src="./61ec72b3b00e0e6c8f43d568f4f106f0bb1d8e45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.261ex; height:2.843ex;" alt="{\displaystyle i\ll \log(N)}" loading="lazy"> then BITMAP[i] is certainly 1</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\approx \log(N)}</annotation>

</semantics>

</math><img src="./14032f27d1d87c680d74dd82da819dce218962f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.746ex; height:2.843ex;" alt="{\displaystyle i\approx \log(N)}" loading="lazy"> then BITMAP[i] is a fringes of 0's and 1's</li></ul>

<div class="mw-heading mw-heading6"><h6 id="K-minimum_value_algorithm">K-minimum value algorithm</h6></div>

The previous algorithm describes the first attempt to approximate F0 in the data stream by Flajolet and Martin. Their algorithm picks a random <a href="Hash_function" title="Hash function">hash function</a> which they assume to uniformly distribute the hash values in hash space.

Bar-Yossef et al. in <a href="#cite_note-:2-10">[10]</a> introduced k-minimum value algorithm for determining number of distinct elements in data stream. They used a similar hash function h which can be normalized to [0,1] as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h:[m]\rightarrow [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h:[m]\rightarrow [0,1]}</annotation>

</semantics>

</math><img src="./57eaf517acf5d0e206c5f3e995334d9804564b77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.877ex; height:2.843ex;" alt="{\displaystyle h:[m]\rightarrow [0,1]}" loading="lazy">. But they fixed a limit t to number of values in hash space. The value of t is assumed of the order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}">

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}</annotation>

</semantics>

</math><img src="./036a615b446f7a66f8c63e64530496706e09a860.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:8.555ex; height:6.176ex;" alt="{\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}" loading="lazy"> (i.e. less approximation-value ε requires more t). KMV algorithm keeps only t-smallest hash values in the hash space. After all the m values of stream have arrived, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \upsilon =\mathrm {Max} (h(a_{i}))}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \upsilon =\mathrm {Max} (h(a_{i}))}</annotation>

</semantics>

</math><img src="./7af025e6cd359d192dce17bb340a6137252e041b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.862ex; height:2.843ex;" alt="{\displaystyle \upsilon =\mathrm {Max} (h(a_{i}))}" loading="lazy"> is used to calculate<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F'_{0}={\dfrac {t}{\upsilon }}}">

</mrow>

</msubsup>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F'_{0}={\dfrac {t}{\upsilon }}}</annotation>

</semantics>

</math><img src="./8bc7c5718371fd127dc4ffea0be39f7eea9c7427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:7.739ex; height:5.176ex;" alt="{\displaystyle F'_{0}={\dfrac {t}{\upsilon }}}" loading="lazy">. That is, in a close-to uniform hash space, they expect at-least t elements to be less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\dfrac {t}{F_{0}}}\right)}">

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\dfrac {t}{F_{0}}}\right)}</annotation>

</semantics>

</math><img src="./2ebebf7aacba8abdefb270f417c5398b0a2234de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:8.967ex; height:6.176ex;" alt="{\displaystyle O\left({\dfrac {t}{F_{0}}}\right)}" loading="lazy">.<pre>Procedure 2 K-Minimum Value

Initialize first t values of KMV

for a in a1 to an do

if h(a) < Max(KMV) then

Remove Max(KMV) from KMV set

Insert h(a) to KMV

end if

end for

return t/Max(KMV)

</pre>

<div class="mw-heading mw-heading6"><h6 id="Complexity_analysis_of_KMV">Complexity analysis of KMV</h6></div>

KMV algorithm can be implemented in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)}">

<mrow>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)}</annotation>

</semantics>

</math><img src="./d0354db6ee1dfc5cb9f2628ed8f761cf737f28e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:20.477ex; height:6.176ex;" alt="{\displaystyle O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)}" loading="lazy"> memory bits space. Each hash value requires space of order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(m))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(m))}</annotation>

</semantics>

</math><img src="./1e50bfd633371255c84bdf58fb6fe2585b3c11e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.404ex; height:2.843ex;" alt="{\displaystyle O(\log(m))}" loading="lazy"> memory bits. There are hash values of the order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}">

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}</annotation>

</semantics>

</math><img src="./036a615b446f7a66f8c63e64530496706e09a860.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:8.555ex; height:6.176ex;" alt="{\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}" loading="lazy">. The access time can be reduced if we store the t hash values in a binary tree. Thus the time complexity will be reduced to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)}">

<mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)}</annotation>

</semantics>

</math><img src="./9b121d93364465d40457d165069a1f4b138e9599.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:22.474ex; height:6.176ex;" alt="{\displaystyle O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)}" loading="lazy">.

<div class="mw-heading mw-heading5"><h5 id="Calculating_Fk">Calculating Fk</h5></div>

Alon et al. estimates Fk by defining random variables that can be computed within given space and time.<a href="#cite_note-:1-3">[3]</a> The expected value of random variables gives the approximate value of Fk.

Assume length of sequence m is known in advance. Then construct a random variable X as follows:

<ul><li>Select ap be a random member of sequence A with index at p, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{p}=l\in (1,2,3,\ldots ,n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{p}=l\in (1,2,3,\ldots ,n)}</annotation>

</semantics>

</math><img src="./a53fdbe8da92c48fef0834ec0d1e6575b85de90a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.859ex; height:3.009ex;" alt="{\displaystyle a_{p}=l\in (1,2,3,\ldots ,n)}" loading="lazy"></li>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=|\{q:q\geq p,a_{q}=l\}|}</annotation>

</semantics>

</math><img src="./a49e2c81c61cd447c8b71aa62a74d6bad0cb992d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.154ex; height:3.009ex;" alt="{\displaystyle r=|\{q:q\geq p,a_{q}=l\}|}" loading="lazy">, represents the number of occurrences of l within the members of the sequence A following ap.</li>

<li>Random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=m(r^{k}-(r-1)^{k})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=m(r^{k}-(r-1)^{k})}</annotation>

</semantics>

</math><img src="./a2c16aa487a3b3458f4042992d1b7116b0254ecb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.855ex; height:3.176ex;" alt="{\displaystyle X=m(r^{k}-(r-1)^{k})}" loading="lazy">.</li></ul>

Assume S1 be of the order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{1-1/k}/\lambda ^{2})}">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{1-1/k}/\lambda ^{2})}</annotation>

</semantics>

</math><img src="./f9b593e70685aa10a56d9835bf1d750b7d1f5464.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.382ex; height:3.343ex;" alt="{\displaystyle O(n^{1-1/k}/\lambda ^{2})}" loading="lazy"> and S2 be of the order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(1/\varepsilon ))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(1/\varepsilon ))}</annotation>

</semantics>

</math><img src="./c76e793c79f6e276041a69d2783fae941d7e2a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.772ex; height:2.843ex;" alt="{\displaystyle O(\log(1/\varepsilon ))}" loading="lazy">. Algorithm takes S2 random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{1},Y_{2},...,Y_{S2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{1},Y_{2},...,Y_{S2}}</annotation>

</semantics>

</math><img src="./cc42c7b40b1352edf34ce5e3d872a6f807b757ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.478ex; height:2.509ex;" alt="{\displaystyle Y_{1},Y_{2},...,Y_{S2}}" loading="lazy"> and outputs the median <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> . Where Yi is the average of Xij where 1 ≤ j ≤ S1.

Now calculate expectation of random variable E(X).

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{k}-(j-1)^{k})\\&=&{\frac {m}{m}}[(1^{k}+(2^{k}-1^{k})+\ldots +(m_{1}^{k}-(m_{1}-1)^{k}))\\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{2}^{k}-(m_{2}-1)^{k}))+\ldots \\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{n}^{k}-(m_{n}-1)^{k}))]\\&=&\sum _{i=1}^{n}m_{i}^{k}=F_{k}\end{array}}}</annotation>

</semantics>

</math><img src="./7442038574e9d21346d4a86c5f298ec384719a01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.123ex; margin-bottom: -0.215ex; width:63.663ex; height:17.843ex;" alt="{\displaystyle {\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{k}-(j-1)^{k})\\&=&{\frac {m}{m}}[(1^{k}+(2^{k}-1^{k})+\ldots +(m_{1}^{k}-(m_{1}-1)^{k}))\\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{2}^{k}-(m_{2}-1)^{k}))+\ldots \\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{n}^{k}-(m_{n}-1)^{k}))]\\&=&\sum _{i=1}^{n}m_{i}^{k}=F_{k}\end{array}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading6"><h6 id="Complexity_of_Fk">Complexity of Fk</h6></div>

From the algorithm to calculate Fk discussed above, we can see that each random variable X stores value of ap and r. So, to compute X we need to maintain only log(n) bits for storing ap and log(n) bits for storing r. Total number of random variable X will be the ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}*S_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}*S_{2}}</annotation>

</semantics>

</math><img src="./23c57ca5f2ba12faa34d8fef22d3c54a043466b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.153ex; height:2.509ex;" alt="{\displaystyle S_{1}*S_{2}}" loading="lazy">⁠.

Hence the total space complexity the algorithm takes is of the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}">

<mrow>

<mrow>

<mfrac>

<mrow>

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mstyle>

</mrow>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}</annotation>

</semantics>

</math><img src="./760fbfaabfeb0aefb0588616a2d3801b73f3aaa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:33.742ex; height:7.676ex;" alt="{\displaystyle O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}" loading="lazy">

<div class="mw-heading mw-heading6"><h6 id="Simpler_approach_to_calculate_F2">Simpler approach to calculate F2</h6></div>

The previous algorithm calculates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{2}}</annotation>

</semantics>

</math><img src="./0fd17e0779153d765b40ebef91533489b87b2e37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{2}}" loading="lazy"> in order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {n}}(\log m+\log n))}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {n}}(\log m+\log n))}</annotation>

</semantics>

</math><img src="./c9d32111316f8422e12d9bbfa883737eba3cb101.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.716ex; height:3.009ex;" alt="{\displaystyle O({\sqrt {n}}(\log m+\log n))}" loading="lazy"> memory bits. Alon et al. in <a href="#cite_note-:1-3">[3]</a> simplified this algorithm using four-wise independent random variable with values mapped to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{-1,1\}}</annotation>

</semantics>

</math><img src="./c0ffb8c7a09dad8456eee3669ee9a7e462fe3c34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.492ex; height:2.843ex;" alt="{\displaystyle \{-1,1\}}" loading="lazy">.

This further reduces the complexity to calculate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{2}}</annotation>

</semantics>

</math><img src="./0fd17e0779153d765b40ebef91533489b87b2e37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{2}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}">

<mrow>

<mrow>

<mfrac>

<mrow>

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mstyle>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}</annotation>

</semantics>

</math><img src="./8a0796aeb236b6c64a6781153137cd2a476e7ec3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:26.884ex; height:7.676ex;" alt="{\displaystyle O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Frequent_elements">Frequent elements</h3></div>

In the data stream model, the frequent elements problem is to output a set of elements that constitute more than some fixed fraction of the stream. A special case is the majority problem, which is to determine whether or not any value constitutes a majority of the stream.

More formally, fix some positive constant <var style="padding-right: 1px;">c</var> > 1, let the length of the stream be <var style="padding-right: 1px;">m</var>, and let <var style="padding-right: 1px;">f</var><var style="padding-right: 1px;">i</var> denote the frequency of value <var style="padding-right: 1px;">i</var> in the stream. The frequent elements problem is to output the <a href="Set_(mathematics)" title="Set (mathematics)">set</a> { <var style="padding-right: 1px;">i</var> | <var style="padding-right: 1px;">f</var><var style="padding-right: 1px;">i</var> > m/c }.<a href="#cite_note-13">[13]</a>

Some notable algorithms are:

<ul><li><a href="Boyer%E2%80%93Moore_majority_vote_algorithm" title="Boyer–Moore majority vote algorithm">Boyer–Moore majority vote algorithm</a></li>

<li><a href="Count-Min_sketch" class="mw-redirect" title="Count-Min sketch">Count-Min sketch</a></li>

<li><a href="Lossy_Count_Algorithm" title="Lossy Count Algorithm">Lossy counting</a></li>

<li>Multi-stage <a href="Bloom_filter" title="Bloom filter">Bloom filters</a></li>

<li><a href="Misra%E2%80%93Gries_heavy_hitters_algorithm" title="Misra–Gries heavy hitters algorithm">Misra–Gries heavy hitters algorithm</a></li>

<li><a href="Misra%E2%80%93Gries_summary" title="Misra–Gries summary">Misra–Gries summary</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Event_detection">Event detection</h3></div>

Detecting events in data streams is often done using a heavy hitters algorithm as listed above: the most frequent items and their frequency are determined using one of these algorithms, then the largest increase over the previous time point is reported as trend. This approach can be refined by using exponentially weighted <a href="Moving_average" title="Moving average">moving averages</a> and variance for normalization.<a href="#cite_note-14">[14]</a>

<div class="mw-heading mw-heading3"><h3 id="Counting_distinct_elements">Counting distinct elements</h3></div>

Counting the number of distinct elements in a stream (sometimes called the

F0 moment) is another problem that has been well studied.

The first algorithm for it was proposed by Flajolet and Martin. In 2010, <a href="Daniel_Kane_(mathematician)" title="Daniel Kane (mathematician)">Daniel Kane</a>, <a href="Jelani_Nelson" title="Jelani Nelson">Jelani Nelson</a> and David Woodruff found an asymptotically optimal algorithm for this problem.<a href="#cite_note-15">[15]</a> It uses O(ε2 + log d) space, with O(1) worst-case update and reporting times, as well as universal hash functions and a r-wise independent hash family where r = Ω(log(1/ε) / log log(1/ε)).

<div class="mw-heading mw-heading3"><h3 id="Entropy">Entropy</h3></div>

The (empirical) entropy of a set of frequencies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {a} }</annotation>

</semantics>

</math><img src="./1a957216653a9ee0d0133dcefd13fb75e36b8b9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.299ex; height:1.676ex;" alt="{\displaystyle \mathbf {a} }" loading="lazy"> is

defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}}</annotation>

</semantics>

</math><img src="./12e8c0ad667f140609b695bf6952b9eb63163e89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:22.032ex; height:6.843ex;" alt="{\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=\sum _{i=1}^{n}a_{i}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=\sum _{i=1}^{n}a_{i}}</annotation>

</semantics>

</math><img src="./d1608ef7a6bdb57aaad3d8b076bab2721528f549.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:10.91ex; height:6.843ex;" alt="{\displaystyle m=\sum _{i=1}^{n}a_{i}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Online_learning">Online learning</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Online_machine_learning" title="Online machine learning">Online machine learning</a></div>

Learn a model (e.g. a <a href="Statistical_classification" title="Statistical classification">classifier</a>) by a single pass over a training set.

<ul><li><a href="Feature_hashing" title="Feature hashing">Feature hashing</a></li>

<li><a href="Stochastic_gradient_descent" title="Stochastic gradient descent">Stochastic gradient descent</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Lower_bounds">Lower bounds</h2></div>

Lower bounds have been computed for many of the data streaming problems

that have been studied. By far, the most common technique for computing

these lower bounds has been using <a href="Communication_complexity" title="Communication complexity">communication complexity</a>.

<ul><li><a href="Data_stream_mining" title="Data stream mining">Data stream mining</a></li>

<li><a href="Data_stream_clustering" title="Data stream clustering">Data stream clustering</a></li>

<li><a href="Online_algorithm" title="Online algorithm">Online algorithm</a></li>

<li><a href="Stream_processing" title="Stream processing">Stream processing</a></li>

<li><a href="Sequential_algorithm" title="Sequential algorithm">Sequential algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMunroPaterson1978" class="citation conference cs1">Munro, J. Ian; Paterson, Mike (1978). "Selection and Sorting with Limited Storage". 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16–18 October 1978. IEEE Computer Society. pp. 253–258. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1978.32">10.1109/SFCS.1978.32</a>.</cite>

</li>

<li id="cite_note-:0-2">^ <a href="#cite_ref-:0_2-0">a</a> <a href="#cite_ref-:0_2-1">b</a> <a href="#cite_ref-:0_2-2">c</a> <a href="#CITEREFFlajoletMartin1985">Flajolet & Martin (1985)</a>

</li>

<li id="cite_note-:1-3">^ <a href="#cite_ref-:1_3-0">a</a> <a href="#cite_ref-:1_3-1">b</a> <a href="#cite_ref-:1_3-2">c</a> <a href="#cite_ref-:1_3-3">d</a> <a href="#CITEREFAlonMatiasSzegedy1996">Alon, Matias & Szegedy (1996)</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFFeigenbaumSampath2005" class="citation journal cs1">Feigenbaum, Joan; Sampath, Kannan (2005). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2005.09.013">"On graph problems in a semi-streaming model"</a>. Theoretical Computer Science. 348 (2): 207–216. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2005.09.013">10.1016/j.tcs.2005.09.013</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBabcockBabuDatarMotwani2002" class="citation book cs1">Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). "Models and issues in data stream systems". Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '02. New York, NY, USA: ACM. pp. 1–16. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.190">10.1.1.138.190</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F543613.543615">10.1145/543613.543615</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-58113-507-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2071130">2071130</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFBar-YossefJayramKumarSivakumar2002" class="citation book cs1">Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; <a href="Luca_Trevisan" title="Luca Trevisan">Trevisan, Luca</a> (2002-09-13). "Counting Distinct Elements in a Data Stream". Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science. Vol. 2483. Springer, Berlin, Heidelberg. pp. 1–10. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.6276">10.1.1.12.6276</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45726-7_1">10.1007/3-540-45726-7_1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-45726-8</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4684185">4684185</a>.</cite>

</li>

<li id="cite_note-turnstile-7"><a href="#cite_ref-turnstile_7-0">^</a> <a href="#CITEREFGilbertKotidisMuthukrishnanStrauss2001">Gilbert et al. (2001)</a>

</li>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFIndykWoodruff2005" class="citation book cs1">Indyk, Piotr; Woodruff, David (2005-01-01). "Optimal approximations of the frequency moments of data streams". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. STOC '05. New York, NY, USA: ACM. pp. 202–208. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1060590.1060621">10.1145/1060590.1060621</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-58113-960-0</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7911758">7911758</a>.</cite>

</li>

<li id="cite_note-:2-10">^ <a href="#cite_ref-:2_10-0">a</a> <a href="#cite_ref-:2_10-1">b</a> <cite id="CITEREFBar-YossefJayramKumarSivakumar2002" class="citation book cs1">Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). Rolim, José D. P.; Vadhan, Salil (eds.). Counting Distinct Elements in a Data Stream. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1–10. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.6276">10.1.1.12.6276</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45726-7_1">10.1007/3-540-45726-7_1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-44147-2</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4684185">4684185</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <a href="#CITEREFMorris1978">Morris (1978)</a>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFFlajolet1985" class="citation journal cs1">Flajolet, Philippe (1985-03-01). "Approximate counting: A detailed analysis". BIT Numerical Mathematics. 25 (1): 113–134. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5320">10.1.1.64.5320</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01934993">10.1007/BF01934993</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0006-3835">0006-3835</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2809103">2809103</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFCormode2014" class="citation book cs1">Cormode, Graham (2014). "Misra-Gries Summaries". In Kao, Ming-Yang (ed.). Encyclopedia of Algorithms. Springer US. pp. 1–5. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-27848-8_572-1">10.1007/978-3-642-27848-8_572-1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-27848-8</bdi>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFSchubertWeilerKriegel2014" class="citation conference cs1">Schubert, E.; Weiler, M.; <a href="Hans-Peter_Kriegel" title="Hans-Peter Kriegel">Kriegel, H. P.</a> (2014). SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14. pp. 871–880. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2623330.2623740">10.1145/2623330.2623740</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-2956-9</bdi>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <a href="#CITEREFKaneNelsonWoodruff2010">Kane, Nelson & Woodruff (2010)</a>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFAlonMatiasSzegedy1999" class="citation cs2"><a href="Noga_Alon" title="Noga Alon">Alon, Noga</a>; <a href="Yossi_Matias" title="Yossi Matias">Matias, Yossi</a>; <a href="Mario_Szegedy" title="Mario Szegedy">Szegedy, Mario</a> (1999), "The space complexity of approximating the frequency moments", <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>, 58 (1): 137–147, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.1997.1545">10.1006/jcss.1997.1545</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a></cite>. First published as <cite id="CITEREFAlonMatiasSzegedy1996" class="citation cs2">Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), "The space complexity of approximating the frequency moments", <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996)</a>, pp. 20–29, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.131.4984">10.1.1.131.4984</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F237814.237823">10.1145/237814.237823</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89791-785-8</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1627911">1627911</a></cite>.</li>

<li><cite id="CITEREFBabcockBabuDatarMotwani2002" class="citation cs2">Babcock, Brian; Babu, Shivnath; Datar, Mayur; <a href="Rajeev_Motwani" title="Rajeev Motwani">Motwani, Rajeev</a>; <a href="Jennifer_Widom" title="Jennifer Widom">Widom, Jennifer</a> (2002), "Models and issues in data stream systems", <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170709081550/http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf">Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002)</a> (PDF), pp. 1–16, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.190">10.1.1.138.190</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F543613.543615">10.1145/543613.543615</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-58113-507-7</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2071130">2071130</a>, archived from <a rel="nofollow" class="external text" href="http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf">the original</a> (PDF) on 2017-07-09, retrieved 2013-07-15</cite>.</li>

<li><cite id="CITEREFFlajoletMartin1985" class="citation journal cs1">Flajolet, Philippe; Martin, G. Nigel (1985). <a rel="nofollow" class="external text" href="http://algo.inria.fr/flajolet/Publications/FlMa85.pdf">"Probabilistic counting algorithms for data base applications"</a> (PDF). Journal of Computer and System Sciences. 31 (2): 182–209. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2885%2990041-8">10.1016/0022-0000(85)90041-8</a>. Retrieved 2016-12-11.</cite></li>

<li><cite id="CITEREFGilbertKotidisMuthukrishnanStrauss2001" class="citation cs2"><a href="Anna_C._Gilbert" title="Anna C. Gilbert">Gilbert, A. C.</a>; Kotidis, Y.; <a href="S._Muthukrishnan_(computer_scientist)" title="S. Muthukrishnan (computer scientist)">Muthukrishnan, S.</a>; Strauss, M. J. (2001), <a rel="nofollow" class="external text" href="http://www.vldb.org/conf/2001/P079.pdf">"Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries"</a> (PDF), Proceedings of the International Conference on Very Large Data Bases: 79–88</cite>.</li>

<li><cite id="CITEREFKaneNelsonWoodruff2010" class="citation conference cs1">Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "An optimal algorithm for the distinct elements problem". Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '10. New York, NY, USA: ACM. pp. 41–52. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.142">10.1.1.164.142</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1807085.1807094">10.1145/1807085.1807094</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-0033-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10006932">10006932</a>.</cite>.</li>

<li><cite id="CITEREFKarpPapadimitriouShenker2003" class="citation cs2"><a href="Richard_Karp" class="mw-redirect" title="Richard Karp">Karp, R. M.</a>; <a href="Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou, C. H.</a>; <a href="Scott_Shenker" title="Scott Shenker">Shenker, S.</a> (2003), "A simple algorithm for finding frequent elements in streams and bags", ACM Transactions on Database Systems, 28 (1): 51–55, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.8530">10.1.1.116.8530</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F762471.762473">10.1145/762471.762473</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:952840">952840</a></cite>.</li>

<li><cite id="CITEREFLallSekarOgiharaXu2006" class="citation conference cs1">Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006). "Data streaming algorithms for estimating entropy of network traffic". Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006). p. 145. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1140277.1140295">10.1145/1140277.1140295</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1802%2F2537">1802/2537</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-59593-319-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:240982">240982</a>.</cite>.</li>

<li><cite id="CITEREFXu2007" class="citation cs2">Xu, Jun (Jim) (2007), <a rel="nofollow" class="external text" href="http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf">A Tutorial on Network Data Streaming</a> (PDF)</cite>.</li>

<li>Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., "Learning Nested Concepts With Limited Storage", Proceeding IJCAI'91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, Pages 777–782, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1991</li>

<li><cite id="CITEREFMorris1978" class="citation cs2">Morris, Robert (1978), "Counting large numbers of events in small registers", Communications of the ACM, 21 (10): 840–842, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359619.359627">10.1145/359619.359627</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:36226357">36226357</a></cite>.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures_and_algorithms145" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_structures_and_algorithms145" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a> and <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data structures</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick tree</a></li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms and <a href="Algorithmic_paradigm" title="Algorithmic paradigm">algorithmic paradigms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Backtracking" title="Backtracking">Backtracking</a></li>

<li><a href="Binary_search" title="Binary search">Binary search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Brute-force_search" title="Brute-force search">Brute-force search</a></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a></li>

<li><a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">Divide and conquer</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Graph_traversal" title="Graph traversal">Graph traversal</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy</a></li>

<li><a href="Hash_function" title="Hash function">Hash function</a></li>

<li><a href="Minimax" title="Minimax">Minimax</a></li>

<li><a href="Online_algorithm" title="Online algorithm">Online</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion</a></li>

<li><a href="Root-finding_algorithm" title="Root-finding algorithm">Root-finding</a></li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting</a></li>

<li><a href="Sweep_line_algorithm" title="Sweep line algorithm">Sweep line</a></li>

<li><a href="String-searching_algorithm" title="String-searching algorithm">String-searching</a></li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li>

<li><a href="List_of_algorithms" title="List of algorithms">List of algorithms</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-22" href="https://en.wikipedia.org/wiki/?title=Streaming_algorithm&oldid=1301990008">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>